package Sort;

import java.util.Arrays;
import java.util.Stack;

//时间复杂度：
//最好情况：完全二叉树(N*logN)一层为N
//最坏情况：单分支树O(N^2)一层为N
public class QuickSort {

    public static void quickSortHoare(int[] array){
        quick(array,0,array.length-1);
    }

    public static void quick(int[] array, int start, int end){
     if(start>=end){
         return;
     }
     int tmp = partition(array,start, end);
     //左边
     quick(array,start,tmp-1);
     //右边
     quick(array,tmp+1,end);

    }

    //优化
    public static void quick2(int[] array, int start, int end){
        if(start>=end){
            return;
        }
        //取中间值下标
        int mid = midOf(array,start,end);
        //保证每一次都是中间
        swap(array,mid,start);
        int tmp = partition(array,start, end);
        //左边
        quick(array,start,tmp-1);
        //右边
        quick(array,tmp+1,end);

    }
    //三数取中
    public static int midOf(int[] array,int start,int end){
        int mid = (start+end)/2;
        if(array[start]>array[end]){
            if(array[start]>array[mid]){
                return start;
            }else if(array[end]<array[mid]){
                return end;
            }else {
                return mid;
            }
        }else {
            if(array[start]>array[mid]){
                return mid;
            }else if(array[end]<array[mid]){
                return end;
            }else {
                return start;
            }
        }
    }


    //方法1
    //找分割点
    public static int partition(int[] array,int left,int right) {
        int key = array[left];
        int i = left;
        while(left<  right) {
            //避免越界问题
            //先看右边，相遇点内数据会比left下标的大
            while (left < right && key <= array[right]) {
                right--;
            }
            while (left < right && key >= array[left]) {
                left++;
            }
            swap(array, left, right);
        }
        //交换分割点和起始点位置
        swap(array,left,i);

        return left;
    }

    //方法2:挖坑法
    public static int partition2(int[] array,int left,int right){
        int key = array[left];
        while(left<right) {
            //找比key大的
            while (left < right && array[right] >= key) {
                right--;
            }
            array[left] = array[right];
            //找比key小的
            while (left < right && array[left] <= key) {
                left++;
            }
            array[right] = array[left];
        }
        //找到的分割点
        array[left] = key;
        return left;
    }

//    方法3： 双指针法
    public static int partition3(int[] array, int left, int right) {
        int cur = left + 1;
        int prv = left;

        while (cur <= right) {
            // 快的指针找比基准值小的
            if (array[cur] <= array[left]) {
                //prv标记位置，保证了prv左侧的元素都小于等于基准值。
                prv++;//必须先加，腾出新的位置。
                swap(array, cur, prv);
            }
            cur++;
        }
        //循环结束，prv标记的位置肯定比基准值小，所有和基准值交换
        swap(array, prv, left);
        return prv;
    }

//使用非递归的方式进行快速排序
    public static void quickSortNor(int[] array){
        Stack<Integer> stack = new Stack<>();
        int start = 0;
        int end = array.length-1;
        int prv = partition2(array,start,end);
        //分割线左边不止一个元素
        if(prv-1>start){
            stack.push(start);
            stack.push(prv-1);
        }

        if(prv+1<end){
            stack.push(prv+1);
            stack.push(end);
        }
        while(!stack.isEmpty()){
            end = stack.pop();
            start = stack.pop();
            prv= partition2(array,start,end);
            if(prv-1>start){
                stack.push(start);
                stack.push(prv-1);
            }

            if(prv+1<end){
                stack.push(prv+1);
                stack.push(end);
            }
        }
    }

    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    public static void  TestSort(int[] array){
        int[] tmp = Arrays.copyOf(array,array.length);
        long time1 = System.currentTimeMillis();
        quickSortHoare(tmp);
        long time2 = System.currentTimeMillis();
        System.out.println("排序用时："+(time2-time1));

    }

    //创建最坏情况的排序
    public static void createArray(int[] array){
        for (int i = 0; i < array.length ; i++) {
            array[i] = array.length-i;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[1_0000];
        //完全逆序
        createArray(array);
        TestSort(array);
    }
}
